{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Number of Vertices to Reach All Nodes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #graph"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #图"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findSmallestSetOfVertices"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #可以到达所有点的最少点数目"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个 <strong>有向无环图</strong>&nbsp;， <code>n</code>&nbsp;个节点编号为 <code>0</code>&nbsp;到 <code>n-1</code>&nbsp;，以及一个边数组 <code>edges</code>&nbsp;，其中 <code>edges[i] = [from<sub>i</sub>, to<sub>i</sub>]</code>&nbsp;表示一条从点&nbsp;&nbsp;<code>from<sub>i</sub></code>&nbsp;到点&nbsp;<code>to<sub>i</sub></code>&nbsp;的有向边。</p>\n",
    "\n",
    "<p>找到最小的点集使得从这些点出发能到达图中所有点。题目保证解存在且唯一。</p>\n",
    "\n",
    "<p>你可以以任意顺序返回这些节点编号。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/08/22/5480e1.png\" style=\"height: 181px; width: 231px;\"></p>\n",
    "\n",
    "<pre><strong>输入：</strong>n = 6, edges = [[0,1],[0,2],[2,5],[3,4],[4,2]]\n",
    "<strong>输出：</strong>[0,3]\n",
    "<strong>解释：</strong>从单个节点出发无法到达所有节点。从 0 出发我们可以到达 [0,1,2,5] 。从 3 出发我们可以到达 [3,4,2,5] 。所以我们输出 [0,3] 。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/08/22/5480e2.png\" style=\"height: 201px; width: 201px;\"></p>\n",
    "\n",
    "<pre><strong>输入：</strong>n = 5, edges = [[0,1],[2,1],[3,1],[1,4],[2,4]]\n",
    "<strong>输出：</strong>[0,2,3]\n",
    "<strong>解释：</strong>注意到节点 0，3 和 2 无法从其他节点到达，所以我们必须将它们包含在结果点集中，这些点都能到达节点 1 和 4 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>2 &lt;= n &lt;= 10^5</code></li>\n",
    "\t<li><code>1 &lt;= edges.length &lt;= min(10^5, n * (n - 1) / 2)</code></li>\n",
    "\t<li><code>edges[i].length == 2</code></li>\n",
    "\t<li><code>0 &lt;= from<sub>i,</sub>&nbsp;to<sub>i</sub> &lt; n</code></li>\n",
    "\t<li>所有点对&nbsp;<code>(from<sub>i</sub>, to<sub>i</sub>)</code>&nbsp;互不相同。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-number-of-vertices-to-reach-all-nodes](https://leetcode.cn/problems/minimum-number-of-vertices-to-reach-all-nodes/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-number-of-vertices-to-reach-all-nodes](https://leetcode.cn/problems/minimum-number-of-vertices-to-reach-all-nodes/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['6\\n[[0,1],[0,2],[2,5],[3,4],[4,2]]', '5\\n[[0,1],[2,1],[3,1],[1,4],[2,4]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestSetOfVertices(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        rd = [0 for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            rd[y] += 1\n",
    "        ans = []\n",
    "        for i in range(n):\n",
    "            if not rd[i]:\n",
    "                ans.append(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestSetOfVertices(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        indegree = [0] * n\n",
    "        for edge in edges:\n",
    "            indegree[edge[1]] += 1\n",
    "        return [node for node in range(len(indegree)) if indegree[node] == 0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestSetOfVertices(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        endSet = set(y for x, y in edges)\n",
    "        ans = [i for i in range(n) if i not in endSet]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestSetOfVertices(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        s = [-1] * n\n",
    "        ans = []\n",
    "        for u,v in edges:\n",
    "            s[v] += 1\n",
    "        for i in range(n):\n",
    "            if s[i] == -1:\n",
    "                ans.append(i)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestSetOfVertices(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        points = set(range(0, n))\n",
    "        # 寻找没人指向的点\n",
    "        for _, p in edges:\n",
    "            points.discard(p)\n",
    "        return list(points)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestSetOfVertices(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        points = set(range(0, n))\n",
    "        # 寻找没人指向的点\n",
    "        for _, p in edges:\n",
    "            points.discard(p)\n",
    "        return list(points)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestSetOfVertices(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        # 寻找入度为0的点\n",
    "        res = set()\n",
    "        for x,y in edges:\n",
    "            res.add(y)\n",
    "        return [x for x in range(n) if x not in res]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestSetOfVertices(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        nodes = set(range(n))\n",
    "        for edge in edges:\n",
    "            if edge[1] in nodes:\n",
    "                nodes.remove(edge[1])\n",
    "        return list(nodes)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestSetOfVertices(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        ins = set(i for i in range(n))\n",
    "        for e in edges:\n",
    "            ins.discard(e[1])\n",
    "        return list(ins)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestSetOfVertices(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        # 找到所有入度为0的点就是结果\n",
    "        res=[[0]*2 for _ in range(n)]\n",
    "        for goin,goout in edges:\n",
    "            res[goin][0]+=1\n",
    "            res[goout][1]+=1\n",
    "        ans=[]\n",
    "        for index,(i,j) in enumerate(res):\n",
    "            if j==0:\n",
    "                ans.append(index)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestSetOfVertices(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        base = [[] for _ in range(n)]\n",
    "\n",
    "        for info in edges:\n",
    "            base[info[1]].append(info[0])\n",
    "        \n",
    "        res = []\n",
    "        \n",
    "        for i in range(n):\n",
    "            if base[i] == []:\n",
    "                res.append(i)\n",
    "                \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestSetOfVertices(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        d = [[] for _ in range(n)]\n",
    "        for edge in edges:\n",
    "            d[edge[1]].append(edge[0])\n",
    "        ans = []\n",
    "        for i in range(n):\n",
    "            if not d[i]:\n",
    "                ans.append(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestSetOfVertices(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        #解题思路：\n",
    "        #找到入度为0的所有节点\n",
    "\n",
    "        nums = set([i for i in range(n)])\n",
    "        for a,b in edges:\n",
    "            if b in nums:\n",
    "                nums -= {b}\n",
    "        return list(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestSetOfVertices(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        hashmap = {}\n",
    "        res = []\n",
    "        s = set()\n",
    "        for i in edges:\n",
    "            s.add(i[0])\n",
    "            s.add(i[1])\n",
    "            hashmap[i[1]] = i[1]\n",
    "        for i in s:\n",
    "            if not hashmap.__contains__(i):\n",
    "                res.append(i)\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestSetOfVertices(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        endSet = set(y for x, y in edges)\n",
    "        ans = [i for i in range(n) if i not in endSet]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestSetOfVertices(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        return list({n[0] for n in edges}-{n[1] for n in edges})"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestSetOfVertices(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        from collections import defaultdict\n",
    "        reverse_d = defaultdict(list)\n",
    "        for edge in edges:\n",
    "            reverse_d[edge[1]].append(edge[0])\n",
    "        \n",
    "        root = []\n",
    "        for i in range(n):\n",
    "            if i not in reverse_d.keys():\n",
    "                root.append(i)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestSetOfVertices(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        return list(set(range(n)) - set(j for i, j in edges))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestSetOfVertices(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        return list(set(range(n)) - set(j for i, j in edges))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestSetOfVertices(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        result = set()\n",
    "        dellete = set()\n",
    "        result_last = []\n",
    "        for i in range(len(edges)):\n",
    "            result.add(edges[i][0])\n",
    "            dellete.add(edges[i][1])\n",
    "        for re in result:\n",
    "            if re not in dellete:\n",
    "                result_last.append(re)\n",
    "        return ((result_last))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestSetOfVertices(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        return list(set(range(n)) - set(map(lambda ele: ele[1], edges)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestSetOfVertices(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        g = defaultdict(list)\n",
    "        cnts = Counter()\n",
    "        \n",
    "        for x, y in edges:\n",
    "            cnts[y] += 1\n",
    "            cnts[x] += 0\n",
    "        ans = []\n",
    "        for k, x in cnts.items():\n",
    "            if x == 0:\n",
    "                ans.append(k)\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestSetOfVertices(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        _d = dict()\n",
    "        for _in, _out in edges:\n",
    "            if _in not in _d:\n",
    "                _d[_in] = 0\n",
    "            if _out not in _d:\n",
    "                _d[_out] = 0\n",
    "            _d[_out] += 1\n",
    "        res = []\n",
    "        for key in _d:\n",
    "            if _d[key] == 0:\n",
    "                res.append(key)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestSetOfVertices(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        dic = defaultdict(int)\n",
    "        for f, t in edges:\n",
    "            dic[t] += 1\n",
    "        return [x for x in range(n) if dic[x] == 0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def findSmallestSetOfVertices(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        f = defaultdict(int)\n",
    "        for e in edges:\n",
    "            b = e[1]\n",
    "            f[b] += 1\n",
    "        ret = []\n",
    "        for i in range(n):\n",
    "            if f[i] == 0:\n",
    "                ret.append(i)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestSetOfVertices(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        ind = defaultdict(int)\n",
    "        for x, y in edges:\n",
    "            ind[y] += 1 \n",
    "        return [j for j in range(n) if ind[j]==0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestSetOfVertices(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        # 入度不为0的集合\n",
    "        inDegrees = set([y for _, y in edges])\n",
    "        return list(set([i for i in range(n)])-inDegrees)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestSetOfVertices(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        ind={i:0 for i in range(n)}\n",
    "\n",
    "        for s,e in edges:\n",
    "            ind[e]+=1\n",
    "        ans=[]\n",
    "        for x in ind:\n",
    "            if ind[x]==0:\n",
    "                ans.append(x)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestSetOfVertices(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        indegree = {i:0 for i in range(n)}\n",
    "\n",
    "        for start, end in edges:\n",
    "            indegree[end] += 1\n",
    "        \n",
    "        result = []\n",
    "        for key, val in indegree.items():\n",
    "            if val == 0:\n",
    "                result.append(key)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestSetOfVertices(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        edges_dict = {'qt': [i[0] for i in edges], 'qa': [i[1] for i in edges]}\n",
    "        num = list(set(edges_dict['qt']).difference(set(edges_dict['qa'])))\n",
    "        return num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestSetOfVertices(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        # def dfs(idx):\n",
    "        #     if flag[idx]:\n",
    "        #         return True\n",
    "        #     else:\n",
    "        #         flag[idx] == True\n",
    "        #         for next in adjancency[idx]:\n",
    "        #             dfs(next)\n",
    "\n",
    "        \n",
    "        flag = [False] * n\n",
    "        adjancency = [[] for _ in range(n)]\n",
    "        indegrees = [0] * n\n",
    "        res = []\n",
    "        \n",
    "        for from_node, to_node in edges:\n",
    "            adjancency[from_node].append(to_node)\n",
    "            indegrees[to_node] += 1\n",
    "            \n",
    "        for i, indegree in enumerate(indegrees):\n",
    "            if indegree == 0:\n",
    "                res.append(i)\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestSetOfVertices(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        info = {}\n",
    "        for i in range(n):\n",
    "            info[i] = 0\n",
    "        \n",
    "        for edge in edges:\n",
    "            info[edge[1]] += 1\n",
    "        \n",
    "        res = []\n",
    "        for i in range(n):\n",
    "            if info[i] == 0:\n",
    "                res.append(i)\n",
    "        \n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestSetOfVertices(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        table = dict(zip(range(n),[0]*n))\n",
    "        for i,j in edges:\n",
    "            table[j]+=1\n",
    "        ans = []\n",
    "        for t in table:\n",
    "            if table[t]==0:\n",
    "                ans.append(t)\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestSetOfVertices(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        # 关键:找入度为零的点\n",
    "        # 建表,记录节点与它的入度出度\n",
    "        vertices = {}   # {node: [in,out]}\n",
    "        for edge in edges:\n",
    "            fm, to = edge[0], edge[1]\n",
    "            if fm not in vertices:\n",
    "                vertices[fm] = [0,1]\n",
    "            else:\n",
    "                vertices[fm][1] += 1\n",
    "            \n",
    "            if to not in vertices:\n",
    "                vertices[to] = [1,0]\n",
    "            else:\n",
    "                vertices[to][0] += 1\n",
    "        # print(vertices)\n",
    "        res = [i for i in vertices if vertices[i][0] == 0]\n",
    "        return res\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestSetOfVertices(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        dc = {}\n",
    "        for e in edges:\n",
    "            dc[e[0]] = dc.get(e[0], [0, 0])\n",
    "            dc[e[0]][0] += 1\n",
    "            dc[e[1]] = dc.get(e[1], [0, 0])\n",
    "            dc[e[1]][1] += 1\n",
    "        res = []\n",
    "        # print(dc)\n",
    "        for k, v in dc.items():\n",
    "            if v[0] and not v[1]:\n",
    "                res.append(k)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestSetOfVertices(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        dict1={}\n",
    "        for i,j in edges:\n",
    "            if i in dict1.keys():\n",
    "                dict1[i].append(j)\n",
    "            else:\n",
    "                dict1[i]=[j]\n",
    "        keys=list(dict1.keys())\n",
    "        k=0\n",
    "        while k<len(keys):\n",
    "            key=keys[k]\n",
    "            if key in dict1.keys():\n",
    "                q=dict1[key]\n",
    "                while q:\n",
    "                    val=q.pop(0)\n",
    "                    if val in dict1.keys():\n",
    "                        q.extend(dict1[val])\n",
    "                        dict1.pop(val)\n",
    "            k+=1\n",
    "        return list(dict1.keys())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestSetOfVertices(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        # a = set()\n",
    "        # b = set()\n",
    "        # for x, y in edges:\n",
    "        #     a.add(x)\n",
    "        #     b.add(y)\n",
    "        # return list(a - b)\n",
    "\n",
    "        # endSet = set(y for x, y in edges)\n",
    "        # ans = [i for i in range(n) if i not in endSet]\n",
    "        # return ans\n",
    "\n",
    "        deg = {}\n",
    "        \n",
    "        for x,y in edges:\n",
    "            if x in deg:\n",
    "                deg[x][1] += 1\n",
    "            else:\n",
    "                deg[x] = [0,1]\n",
    "            if y in deg:\n",
    "                deg[y][0] += 1\n",
    "            else:\n",
    "                deg[y] = [1,0]\n",
    "        \n",
    "        ans = []\n",
    "        for k,v in deg.items():\n",
    "            if v[0] == 0:\n",
    "                ans.append(k)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestSetOfVertices(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        inDegrees = collections.defaultdict(list)\n",
    "        for i, j in edges:\n",
    "            inDegrees[j].append(i)\n",
    "        ans = []\n",
    "        for key in range(n):\n",
    "            if not inDegrees[key]:\n",
    "                ans.append(key)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestSetOfVertices(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        sources = set([_[0] for _ in edges])\n",
    "        target = set([_[1] for _ in edges])\n",
    "        isolated_nodes = set(range(n)) - sources - target\n",
    "        return sorted(list(isolated_nodes | (sources - target)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestSetOfVertices(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        graph = defaultdict(list)\n",
    "        ans = []\n",
    "        for edge in edges:\n",
    "            graph[edge[1]].append(edge[0])\n",
    "        \n",
    "        for node in range(n):\n",
    "            if not graph[node]:\n",
    "                ans.append(node)\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestSetOfVertices(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        res = [i for i in range(0,n)]\n",
    "        s = collections.deque()\n",
    "        for i,v in enumerate(edges):\n",
    "            s.append(v[1])\n",
    "        res = set(res) ^ set(s)\n",
    "        return list(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestSetOfVertices(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        # 找上司\n",
    "        first = set()\n",
    "        # 剪枝\n",
    "        visited = set()\n",
    "        # 用于深度搜索来找根\n",
    "        grap = [[]for _ in range(n)]\n",
    "        for i in edges:\n",
    "            grap[i[1]].append(i[0])\n",
    "        def dfs(start):\n",
    "            # 找到底了\n",
    "            if grap[start]==[]:\n",
    "                first.add(start)\n",
    "            for i in grap[start]:\n",
    "                if i not in visited:\n",
    "                    visited.add(i)\n",
    "                    dfs(i)\n",
    "        for i in range(n):\n",
    "            if i not in visited:\n",
    "                dfs(i)\n",
    "        return list(first)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestSetOfVertices(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        from collections import defaultdict\n",
    "        d = defaultdict(list)\n",
    "        st = [False for _ in range(n)]\n",
    "        for a,b in edges:\n",
    "            d[a].append(b)\n",
    "            st[b]=True\n",
    "        res = []\n",
    "        for i in range(n):\n",
    "            if not st[i]:\n",
    "                res.append(i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestSetOfVertices(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        graph = defaultdict(list)\n",
    "        in_deg = [0] * n\n",
    "        for x, y in edges:\n",
    "            graph[x].append(y)\n",
    "            in_deg[y] += 1\n",
    "        a = [i for i in range(len(in_deg)) if in_deg[i] == 0]\n",
    "        return a\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestSetOfVertices(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "\n",
    "        answerlist = []\n",
    "        for i in range(n):\n",
    "            answerlist.append([i])\n",
    "        \n",
    "        print(answerlist)\n",
    "\n",
    "        for edge in edges:\n",
    "            answerlist[edge[1]].append(edge[0])\n",
    "\n",
    "        print(answerlist)\n",
    "\n",
    "        li = []\n",
    "        for answer in answerlist:\n",
    "            if len(answer) == 1:\n",
    "                li.append(answer[0])\n",
    "\n",
    "        return li\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestSetOfVertices(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        edges = set(tuple(ele) for ele in edges)\n",
    "        counts = Counter(y for _, y in edges)\n",
    "        return [i for i in range(n) if not counts[i]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestSetOfVertices(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        edges = set(tuple(ele) for ele in edges)\n",
    "        counts = Counter(y for _, y in edges)\n",
    "        return [i for i in range(n) if not counts[i]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestSetOfVertices(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        edges.sort()\n",
    "        points = set(i for i in range(n))\n",
    "        destinations = set(val[1] for val in edges)\n",
    "        initStart = points - destinations\n",
    "        reachable = initStart.copy()\n",
    "\n",
    "        m = len(reachable)\n",
    "        while True:\n",
    "            for val in edges:\n",
    "                if val[0] in reachable:\n",
    "                    reachable.add(val[1])\n",
    "            if len(reachable) == m:\n",
    "                break\n",
    "            else:\n",
    "                m = len(reachable)\n",
    "                \n",
    "        if len(reachable) == n:\n",
    "            return list(initStart)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestSetOfVertices(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        dic = collections.defaultdict(list)\n",
    "        indegree = [0] * n\n",
    "        outdegree = [0] * n\n",
    "        for start, end in edges:\n",
    "            dic[start].append(end)\n",
    "            indegree[end] += 1\n",
    "            outdegree[start] += 1\n",
    "\n",
    "        queue, ans = [], []\n",
    "        for i in range(n):\n",
    "            if indegree[i] == 0:\n",
    "                queue.append(i)\n",
    "                ans.append(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestSetOfVertices(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        in_degree = defaultdict(list)\n",
    "        all_node = set(range(n))\n",
    "        for [start,end] in edges:\n",
    "            in_degree[end]+=[start]\n",
    "        start_node = all_node.difference(in_degree.keys())\n",
    "\n",
    "        return list(start_node)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestSetOfVertices(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        ans={x[0] for x in edges}\n",
    "        rmv={x[1] for x in edges}\n",
    "        while 1:\n",
    "            tmp=ans-(ans & rmv)\n",
    "            \n",
    "            if ans==tmp:\n",
    "                return list(ans)\n",
    "            \n",
    "            rmv=rmv | (ans & rmv)\n",
    "            ans=tmp\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestSetOfVertices(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        ans = set()\n",
    "        out_degree = [0] * n\n",
    "        in_map = defaultdict(list)\n",
    "        for s, d in edges:\n",
    "            out_degree[s] += 1\n",
    "            in_map[d].append(s)\n",
    "        while not all([x <= 0 for x in out_degree]):\n",
    "            tails = [i for i, x in enumerate(out_degree) if x == 0]\n",
    "            for tail in tails:\n",
    "                for s in in_map[tail]:\n",
    "                    out_degree[s] -= 1\n",
    "                    if not in_map[s]:\n",
    "                        # print(f\"{s} has not in, ans += 1\")\n",
    "                        ans.add(s)\n",
    "                out_degree[tail] = -1\n",
    "            # print(tails)\n",
    "        return list(ans)\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestSetOfVertices(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        adj = [[] for _ in range(n)]\n",
    "        ingree = [0]*n\n",
    "        for f, t in edges:\n",
    "            adj[f].append(t)\n",
    "            ingree[t] += 1\n",
    "        ans = []\n",
    "        resdict = dict()\n",
    "        for i, v in enumerate(ingree):\n",
    "            if v == 0:\n",
    "                resdict[i] = []\n",
    "        return list(resdict.keys())\n",
    "        # for x in resdict.keys():\n",
    "        #     que = []\n",
    "        #     que.append(x)\n",
    "        #     while que:\n",
    "        #         cur = que.pop()\n",
    "        #         resdict[x].append(cur)\n",
    "        #         for i in adj[cur]:\n",
    "        #             ingree[i] -= 1\n",
    "        #             if ingree[i] == 0:\n",
    "        #                 que.append(i)\n",
    "        # schans = list(resdict.keys())\n",
    "        # schans.sort()\n",
    "        # chkans = []\n",
    "        # mid = []\n",
    "        # def bactrace(index, lenth):\n",
    "        #     if len(mid) == lenth:\n",
    "        #         chkans.append(mid[:])\n",
    "        #         return\n",
    "        #     for i in range(index, len(schans)):\n",
    "        #         mid.append(schans[i])\n",
    "        #         bactrace(i + 1, lenth)\n",
    "        #         mid.pop()\n",
    "\n",
    "        # for l in range(1, len(schans) + 1):\n",
    "        #     bactrace(0, l)\n",
    "\n",
    "        # curlen = 1\n",
    "        # findflag = False\n",
    "        # for item in chkans:\n",
    "        #     curset = set()\n",
    "        #     midans = []\n",
    "        #     if findflag and len(item) > curlen:\n",
    "        #         break\n",
    "        #     curlen = max(curlen, len(item))\n",
    "        #     for i in item:\n",
    "        #         curset |= set(resdict[i])\n",
    "        #         midans.append(i)\n",
    "        #     if len(curset) == n:\n",
    "        #         return midans\n",
    "        #         # findflag = True\n",
    "        #         # ans.append(midans)\n",
    "\n",
    "        # return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestSetOfVertices(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        return list(set(range(n)) ^ set(list(zip(*edges))[1]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestSetOfVertices(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        g = defaultdict(list)\n",
    "        ind = Counter()\n",
    "        for u,v in edges:\n",
    "            g[u].append(v)\n",
    "            ind[v] += 1\n",
    "        r = []\n",
    "        for i in range(n):\n",
    "            if ind[i] == 0:\n",
    "                r.append(i)\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestSetOfVertices(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        dic = {i:[] for i in range(n)}\n",
    "        o = [0 for i in range(n)]\n",
    "        for e in edges:\n",
    "            i = e[0]\n",
    "            j = e[1]\n",
    "            dic[j].append(i)\n",
    "            o[i] += 1\n",
    "        \n",
    "        print(dic,o)\n",
    "\n",
    "        if sum(o)==0:\n",
    "            return [i for i in range(n)]\n",
    "        \n",
    "        f = 1\n",
    "            \n",
    "        while(f==1):\n",
    "            o_n = o.copy()\n",
    "            for oi in range(len(o)):\n",
    "                if o[oi] == 0:\n",
    "                     p = dic[oi]\n",
    "                     if len(p)>0:\n",
    "                        for j in p:\n",
    "                            o_n[j] -= 1\n",
    "                        o_n[oi] = -1\n",
    "            o = o_n\n",
    "            f = 0\n",
    "            for oi in range(len(o)):\n",
    "                if o[oi]>0:\n",
    "                    f = 1\n",
    "                    break\n",
    "            print(o)\n",
    "\n",
    "        r = []\n",
    "        for oi in range(len(o)):\n",
    "            if o[oi] == 0:\n",
    "                r.append(oi)\n",
    "        \n",
    "        return r\n",
    "                    \n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestSetOfVertices(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        cntIn=dict((i,0) for i in range(n))\n",
    "        cntOu=dict((i,0) for i in range(n))\n",
    "\n",
    "        for x in edges:\n",
    "            cntOu[x[0]]+=1\n",
    "            cntIn[x[1]]+=1\n",
    "        \n",
    "        res=[]\n",
    "        for x in cntIn.keys():\n",
    "            if cntIn[x]==0:\n",
    "                res.append(x)\n",
    "        \n",
    "        return res\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestSetOfVertices(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        parent = list(range(n)) \n",
    "        adj = defaultdict(list) \n",
    "        indeg = [0] * n \n",
    "        for u, v in edges: \n",
    "            adj[u].append(v) \n",
    "            indeg[v] += 1\n",
    "\n",
    "        def dfs(u): \n",
    "            for v in adj[u]: \n",
    "                if parent[v] == v: \n",
    "                    parent[v] = u \n",
    "                    dfs(v) \n",
    "        \n",
    "        for i, deg in enumerate(indeg): \n",
    "            if not deg: dfs(i) \n",
    "        \n",
    "        return [i for i in range(n) if parent[i] == i]\n",
    "\n",
    "                \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestSetOfVertices(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        G = [[] for i in range(n)]\n",
    "        indegree = [0 for i in range(n)]\n",
    "        outdegree = [0 for i in range(n)]\n",
    "        for x in edges:\n",
    "            a, b = x[0],x[1]\n",
    "            G[a].append(b)\n",
    "            G[b].append(a)\n",
    "            indegree[b] += 1\n",
    "            outdegree[a] += 1\n",
    "        \n",
    "        ans = []\n",
    "        vis = [0 for i in range(n)]\n",
    "        pos = [i for i in range(n) if indegree[i] == 0 and vis[i] == 0]\n",
    "        def dfs(i):\n",
    "            vis[i] = 1\n",
    "            for node in G[i]:\n",
    "                outdegree[i] -= 1\n",
    "                if vis[node] == 0:\n",
    "                    indegree[node] -= 1\n",
    "                    dfs(node)\n",
    "        while pos != []:\n",
    "            for u in pos:\n",
    "                ans.append(u)\n",
    "                dfs(u)\n",
    "            pos = [i for i in range(n) if indegree[i] == 0 and vis[i] == 0]\n",
    "        return ans\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def findSmallestSetOfVertices(self, n , edges ) :\n",
    "        dict1 = defaultdict(list)\n",
    "        \n",
    "        for s, e in edges:\n",
    "            dict1[e].append(s)\n",
    "        \n",
    "        ans = []\n",
    "        for i in range(n):\n",
    "            if len(dict1[i]) == 0:\n",
    "                ans.append(i)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestSetOfVertices(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        # 若没有点指向该点：必须保留\n",
    "        edgeDict = {}\n",
    "        for edge in edges:\n",
    "            startP, endP = edge[0], edge[1]\n",
    "            if startP in edgeDict:\n",
    "                edgeDict[startP].append(endP)\n",
    "            else:\n",
    "                edgeDict[startP] = [endP]\n",
    "\n",
    "        vis = [0] * n  # 处理过该点与否\n",
    "        linked = [0] * n  # 连接了该点与否\n",
    "        for i in range(n):\n",
    "            vis[i] = 1\n",
    "            if i not in edgeDict:\n",
    "                continue\n",
    "            q = edgeDict[i].copy()\n",
    "            while q:\n",
    "                next_q = []\n",
    "                while q:\n",
    "                    cur = q.pop()\n",
    "                    vis[cur] = 1\n",
    "                    linked[cur] = 1\n",
    "                    if cur not in edgeDict:\n",
    "                        continue\n",
    "\n",
    "                    for k in edgeDict[cur]:\n",
    "                        if not vis[k]:\n",
    "                            next_q.append(k)\n",
    "\n",
    "                q = next_q.copy()\n",
    "            \n",
    "        ans = []\n",
    "        for i in range(len(linked)):\n",
    "            if linked[i] == 0:\n",
    "                ans.append(i)\n",
    "\n",
    "        return ans\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestSetOfVertices(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        revGraph = defaultdict(list)\n",
    "        outDegrees = Counter()\n",
    "        res = []\n",
    "        for u, v in edges:\n",
    "            outDegrees[u] += 1\n",
    "            revGraph[v].append(u)\n",
    "        \n",
    "        queue = deque([u for u in range(n) if outDegrees[u] == 0])\n",
    "        while queue:\n",
    "            u = queue.popleft()\n",
    "            if not revGraph[u]:\n",
    "                res.append(u)\n",
    "            else:\n",
    "                for v in revGraph[u]:\n",
    "                    outDegrees[v] -= 1\n",
    "                    if outDegrees[v] == 0:\n",
    "                        queue.append(v)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestSetOfVertices(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        ind = [0]*(n+1)\n",
    "        mp = {}\n",
    "        for x,y in edges:\n",
    "            ind[y]+=1\n",
    "            mp[x] = mp.get(x,[])\n",
    "            mp[x].append(y)\n",
    "        \n",
    "        vis = set()\n",
    "        ans = []\n",
    "        def dfs(x):\n",
    "            if x in vis:\n",
    "                return \n",
    "            vis.add(x)\n",
    "            for y in mp.get(x,[]):\n",
    "                ind[y] -= 1\n",
    "                if ind[y] == 0:\n",
    "                    dfs(y)\n",
    "        \n",
    "        for i in range(n):\n",
    "            if ind[i] == 0:\n",
    "                if i in vis: \n",
    "                    continue\n",
    "                dfs(i)\n",
    "                ans.append(i)\n",
    "        def dfs_no_ind(x):\n",
    "            if x in vis:\n",
    "                return \n",
    "            vis.add(x)\n",
    "            for y in mp.get(x,[]):\n",
    "                if y not in vis:\n",
    "                    dfs_no_ind(y)\n",
    "        for i in range(n):\n",
    "            if i not in vis:\n",
    "                dfs_no_ind(i)\n",
    "                ans.appned(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestSetOfVertices(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        adj = [[] for _ in range(n)]\n",
    "        adj2 = [[] for _ in range(n)]\n",
    "        for i in range(len(edges)):\n",
    "            adj[edges[i][0]].append(edges[i][1])\n",
    "            adj2[edges[i][1]].append(edges[i][0])\n",
    "        ret = set()\n",
    "        for i in range(n):\n",
    "            if (len(adj2[i]) == 0):\n",
    "                ret.add(i)\n",
    "        visited = [False for _ in range(n)]\n",
    "        from collections import deque\n",
    "        q = deque()\n",
    "        for x in ret:\n",
    "            q.append(x)\n",
    "            visited[x] = True\n",
    "        m = len(q)\n",
    "        while (m > 0):\n",
    "            for i in range(m):\n",
    "                x = q.popleft()\n",
    "                # if (visited[x]): continue\n",
    "                for nxt in adj[x]:\n",
    "                    if (visited[nxt]): continue\n",
    "                    visited[nxt] = True\n",
    "                    q.append(nxt)\n",
    "            m = len(q)\n",
    "        for i in range(n):\n",
    "            if (visited[i]): continue\n",
    "            for x in adj2[i]:\n",
    "                if (x in ret):\n",
    "                    visited[i] = True\n",
    "                    break\n",
    "                else:\n",
    "                    visited[i] = True\n",
    "                    ret.add(x)\n",
    "                    break\n",
    "        return list(ret)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestSetOfVertices(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        record_in = collections.defaultdict(list)\n",
    "        record_out = collections.defaultdict(list)\n",
    "        for i, j in edges:\n",
    "            record_out[i].append(j)\n",
    "            record_in[j].append(i)\n",
    "        return [k for k in record_out if k not in record_in]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestSetOfVertices(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "\n",
    "        nodes = collections.defaultdict(list)\n",
    "\n",
    "        for from_node, to_node in edges:\n",
    "            nodes[to_node].append(from_node)\n",
    "\n",
    "        start_nodes = list(nodes.keys())\n",
    "\n",
    "        res = []\n",
    "        visited = set()\n",
    "        for node in start_nodes:\n",
    "            self.dfs(node, nodes, visited, res)\n",
    "\n",
    "        return res\n",
    "    \n",
    "    def dfs(self, curr, nodes, visited, res):\n",
    "\n",
    "        if curr in visited:\n",
    "            return \n",
    "\n",
    "        visited.add(curr)\n",
    "\n",
    "        if not nodes[curr]:\n",
    "            res.append(curr)\n",
    "            return \n",
    "        \n",
    "        for prev_node in nodes[curr]:\n",
    "            self.dfs(prev_node, nodes, visited, res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestSetOfVertices(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "\n",
    "        g = collections.defaultdict(list)\n",
    "        indegrees = [0]*n\n",
    "        for i, (x, y) in enumerate(edges):\n",
    "            g[x].append(y)\n",
    "            indegrees[y] += 1\n",
    "        res = []\n",
    "        for i in range(n):\n",
    "            if indegrees[i] == 0:\n",
    "                res.append(i)\n",
    "\n",
    "        return res\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestSetOfVertices(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        g_in = [[] for i in range(n)]\n",
    "        g_out = [[] for i in range(n)]\n",
    "        for e in edges:\n",
    "            g_out[e[0]].append(e[1])\n",
    "            g_in[e[1]].append(e[0])\n",
    "        zero_in_set = []\n",
    "        for i, g in enumerate(g_in):\n",
    "            if not g:\n",
    "                zero_in_set.append(i)\n",
    "        return zero_in_set\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestSetOfVertices(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        res, visited = [], set()\n",
    "        \n",
    "        to, f = collections.defaultdict(list), collections.defaultdict(list)\n",
    "        for edge in edges:\n",
    "            to[edge[0]].append(edge[1])\n",
    "            f[edge[1]].append(edge[0])\n",
    "        '''    \n",
    "        for i in range(n):\n",
    "            if i not in visited and i not in f:\n",
    "                q = collections.deque([i])\n",
    "                while q:\n",
    "                    node = q.popleft()\n",
    "                    if node in res:\n",
    "                        res.remove(node)\n",
    "                    if node not in visited and to[node]: \n",
    "                        q.extend(to[node])\n",
    "                    visited.add(node)\n",
    "                res.append(i)\n",
    "        '''\n",
    "        for i in range(n):\n",
    "            if i not in f:\n",
    "                res.append(i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestSetOfVertices(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        visit = [0] * n\n",
    "        paths = defaultdict(list)\n",
    "        indegree = [0] * n\n",
    "        for u, v in edges:\n",
    "            paths[u].append(v)\n",
    "            indegree[v] += 1\n",
    "        return [v for v in range(n) if indegree[v] == 0]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestSetOfVertices(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "\n",
    "        g = collections.defaultdict(list)\n",
    "        in_dg = [0] * n\n",
    "        # out_dg = [0] * n\n",
    "        for e in edges:\n",
    "            g[e[0]].append(g[e[1]])\n",
    "            in_dg[e[1]] += 1\n",
    "            # out_dg[e[0]] += 1\n",
    "        return [i for i in range(n) if in_dg[i]==0]\n",
    "        "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
